import java.util.*;

public class Leetcode1020 {

    public static void main(String[] args) {
        System.out.println(numEnclaves(new int[][]{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}}));
    }

   /* private static final Pair[] around = new Pair[]{
            new Pair(-1, 0),
            new Pair(1, 0),
            new Pair(0, -1),
            new Pair(0, 1),
    };
    static int m;
    static int n;
    static boolean[][] isHandLe;

    public static int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int res = 0;
        isHandLe = new boolean[m][n];

        Queue<Pair> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || j == 0 || i == m - 1 || j == n - 1) && grid[i][j] == 1) {
                    queue.offer(new Pair(i, j));
                    isHandLe[i][j] = true;
                } else if (grid[i][j] == 1) {
                    res++;
                }
            }
        }

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            for (Pair p : around) {
                Pair add = pair.add(p);
                if (add.isNotHandle() && add.isSuccess() && grid[add.x][add.y] == 1) {
                    queue.add(add);
                    isHandLe[add.x][add.y] = true;
                    res--;
                }
            }
        }

        return res;
    }


    static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x && y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        public Pair add(Pair pair) {
            return new Pair(this.x + pair.x, this.y + pair.y);
        }

        public boolean isSuccess() {
            return this.x >= 0 && this.x < m && this.y >= 0 && this.y < n;
        }

        public boolean isNotHandle() {
            if (isSuccess()) {
                return !isHandLe[this.x][this.y];
            } else {
                return false;
            }
        }
    }*/

    public static int numEnclaves(int[][] grid) {
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i);
            dfs(grid, m - 1, i);
        }

        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }

        for (int[] g : grid) {
            for (int j = 0; j < n; j++) {
                res += g[j];
            }
        }
        return res;
    }

    public static void dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) {
            return;
        }
        grid[x][y] = 0;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}
